package com.lry.basic.algorithm.tree;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/7/10
 */
//平衡的二叉排序搜索树
public class BalanceTree {
     Node root;
    public  boolean insert(Node node){
        if(node==null)return false;
        if(root==null){
            root=node;
            return true;
        }

        Node temp = root;
        Node cur = null;
        while(temp!=null){
            cur = temp;
            if(temp.data>node.data){//左边
                temp = temp.left;
            }else if(temp.data<node.data){//右边
                temp = temp.right;
            }else{
                return false;
            }
        }
        if(cur==null)return false;
        if(node.data>cur.data){
            cur.right = node;
        }else{
            cur.left = node;
        }
        //解法错误，原因：不是每次插入都是导致根节点不平衡，有可能导致非根节点不平衡例如4 2 1 3 5 6 7 插入7的时候导致5不平衡
        //解决办法 找到最小不平衡子树的根节点进行下面操作
        Node par = parent(node.data);//par是最佳的调整节点
        while(balance(par)>=-1&&balance(par)<=1){
            if(par==null||par==root)break;
            par = parent(par.data);
        }
        Node parpar = parent(par.data);//保存最佳调整节点的父亲

        boolean left=false,right=false;//记录最佳的调整节点是其父亲的左孩子还是右孩子
        if(parpar!=null&&parpar.left.data==par.data){
            left = true;
        }
        if(parpar!=null&&parpar.right.data==par.data){
            right = true;
        }

        if(balance(par)>1&&node.data<par.left.data){//LL 右旋
            par = rightRotate(par);
        }
        if(balance(par)<-1&&node.data>par.right.data){//RR 左旋
            par = leftRotate(par);
        }
        if(balance(par)>1&&node.data>par.left.data){//LR
            Node cr = leftRotate(par.left);
            par.left = cr;
            par = rightRotate(par);
        }
        if(balance(par)<-1&&node.data<par.right.data){//RL 先右旋 再左旋
            Node cr = rightRotate(par.right);
            par.right = cr;
            par = leftRotate(par);
        }

        if(parpar==null){//说明最佳的旋转节点par是根节点
            root = par;
        }else{
            if(left){
                parpar.left = par;
            }
            if(right){
                parpar.right = par;
            }
        }

        return true;
    }

    public boolean isBalance(Node root){
        boolean flag = true;
        LinkedList<Node> stack = new LinkedList();
        while(!stack.isEmpty()||root!=null){
            //一直往左边走
            while(root!=null){
                if(!(balance(root)>=-1&&balance(root)<=1)){
                    flag = false;
                }
                stack.push(root);
                root = root.left;
            }
            //跳出上面的while循环意味着往左边走到null，此时需要出栈走一次右边
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
        return flag;
    }
    private Node leftRotate(Node root) {
        Node tmp = root;
        Node newRoot = root.right;
        Node newRootLeft = newRoot.left;
        root = newRoot;
        root.left = tmp;
        tmp.right = newRootLeft;
        return root;
    }

    public Node rightRotate(Node root){
        Node tmp = root;
        Node newRoot = root.left;
        Node newRootRight = newRoot.right;
        root = newRoot;
        root.right = tmp;
        tmp.left = newRootRight;
        return root;
    }
    public Node parent(int par){
        Node temp = root;
        Node cur = null;
        while(temp!=null){
            if(temp.data>par){//往左边走
                cur = temp;
                temp = temp.left;
            }else if(temp.data<par){//往右边走
                cur = temp;
                temp=temp.right;
            }else{
                return cur;
            }
        }
        return cur;
    }
    public int balance(Node root){
        return root==null?0:high(root.left)-high(root.right);
    }
    public int high(Node node){
        if(node==null)return 0;
        return Math.max(high(node.left),high(node.right))+1;
    }

    public void inOrder(Node root) {
        if(root!=null){
            inOrder(root.left);
            System.out.print(root.data+" ");
            inOrder(root.right);
        }
    }
    public static void main(String[] args) {
        BalanceTree tree = new BalanceTree();
        Random random = new Random();
        for(int i=0;i<1000;i++){
            tree.insert(new Node(random.nextInt(10000)));
        }
        tree.inOrder(tree.root);
        System.out.println("\r\n"+tree.root);
        System.out.println(tree.isBalance(tree.root));
    }

    static class Node{
        int data;
        Node left;
        Node right;
        Node(int data){
            this.data=data;
        }
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
